
#include <iostream>
#include "QueryExpressionParser.h"

QueryExpressionParser::QueryExpressionParser(PKB *pkb) {
	mPkb = pkb;
	initializeMapOfMathSymbols();
}

QueryExpressionParser::~QueryExpressionParser(void){
}
void QueryExpressionParser::initializeMapOfMathSymbols() {
	mMapOfMathSymbols.insert( std::pair<std::string, int>("+", 1) );
	mMapOfMathSymbols.insert( std::pair<std::string, int>("-", 1) );
	mMapOfMathSymbols.insert( std::pair<std::string, int>("*", 2) );
	mMapOfMathSymbols.insert( std::pair<std::string, int>("(", 3) );
	mMapOfMathSymbols.insert( std::pair<std::string, int>(")", 3) );

	mMapOfMathOperators.insert( std::pair<std::string, TreeNodeType>("+", AST_PLUS) );
	mMapOfMathOperators.insert( std::pair<std::string, TreeNodeType>("-", AST_MINUS) );
	mMapOfMathOperators.insert( std::pair<std::string, TreeNodeType>("*", AST_TIMES) );
}

TreeNode* QueryExpressionParser::convertExpressionToTree(std::string expr) {
	TreeNode* rootNode = NULL;
	// Add spaces so that even expressions like "(1+2+(x+y))" can be evaluated by whitespace tokenizing
	//cout << "*******Converting the expression \"" << expr << "\" into a tree\n";
	//cout << "Adding whitespaces before and after math symbols\n";
	expr = addSpacesToExpressionBeforeAndAfterMathSymbols(expr);
	//cout << "Done adding whitespaces\n";
	//cout << "Tokenizing by whitespaces\n";
	std::vector<std::string> exprTokens = tokenizeByWhitespace(expr);
	//cout << "Done tokenizing\n";
	exprTokens = addBracketsAccordingToPrecedence(exprTokens);
	// Variables for the recursive expression to tree conversion
	int numOfOpenBrackets = 0; // whether or not at the moment there is an open bracket to close
	int currentPosition = 0; // current position to check
	int endPosition = exprTokens.size() - 1;
	//cout << "********Converting expression to tree recursively\n";
	rootNode = convertExpressionToTreeRecursively(exprTokens, &numOfOpenBrackets, &currentPosition, endPosition);
	//cout << "********DONE Converting expression to tree recursively\n";
	//cout << "RootNode reference = " << (int)rootNode << "\n";
	return rootNode;
}

TreeNode* QueryExpressionParser::convertExpressionToTreeRecursively(std::vector<std::string> exprTokens, 
	int *numOfOpenBrackets, int *currentPosition, int endPosition) {
		TreeNode* exprRoot = NULL;
		TreeNode* leftExpr = NULL;
		TreeNode* rightExpr = NULL;
		bool isRightBracketed = false;

		//cout << "endPosition = " << endPosition << "\n";
		//cout << "currentPosition = " << *currentPosition << "\n";
		//cout << "exprTokens size = " << exprTokens.size() << "\n";
		// Error checking
		// Should not be out of bounds
		if ( (*currentPosition > endPosition) ||
				(endPosition >= (int)exprTokens.size()) ) {
			return NULL;
		}
		// Ensure that the start of the expression is valid
		std::string currentToken = exprTokens.at(*currentPosition);
		//cout << "currentToken = \"" << currentToken << "\"\n";
		if ( !isValidStartingToken(currentToken) ) {
			return NULL;
		}

		// Here, currentToken is a VALID starting token,
		// meaning that it is either an
		// 1. open bracket or
		// 2. a variable or
		// 3. a constant integer
		
		// Go to next parsing position
		(*currentPosition)++;

		// Get the leftExpr
		if ( isOpenBracket(currentToken) ) {
			// 1. open bracket
			// Use recursion to parse the bracket expression
			//cout << "Recursively parsing the expression because we ran into an open bracket " << currentToken << "\n";
			(*numOfOpenBrackets)++;
			leftExpr = convertExpressionToTreeRecursively(exprTokens, numOfOpenBrackets, currentPosition, endPosition);
		} else {
			// currentToken is either a variable or a constant, so parse it directly.
			if ( isValidVariableName(currentToken) ) {
				// 2. variable
				int varIndex = getVariableIndexFromPKB(currentToken);
				//cout << "Converting variable " << currentToken << " into TreeNode with varIndex = " << varIndex << endl;
				leftExpr = new TreeNode(AST_VAR, varIndex);
			} else {
				//cout << "Converting constant integer " << currentToken << " into TreeNode\n";
				// 3. constant integer
				int constantInteger = std::stoi(currentToken);
				leftExpr = new TreeNode(AST_CONST, constantInteger);
			}
		}
		if (leftExpr == NULL) {
			// if the left expr is null, that means the expression given is invalid.
			//cout << "leftExpr is NULL for currentPosition = " << *currentPosition - 1 << "\n";
			return NULL;
		}
		//cout << "leftExpr is not null for currentPosition = " << *currentPosition - 1 << "\n";

		// Done with the left expression, 
		// onto the second expression (if there is one!)
		// First, make sure that there is a second expr 
		// (it is possible that an expression only contains one expression,
		// e.g. "x" or "1" or "(1 + x)"
		// If that is the case, then the current position would have become equal to the endPosition!
		if ( *currentPosition > endPosition ) {
			if ( *numOfOpenBrackets == 0 ) {
				return leftExpr;
			} else {
				// end of expression but have unclosed brackets
				return NULL;
			}
		}

		// Move to next token!
		currentToken = exprTokens.at(*currentPosition);

		(*currentPosition)++;

		// For the 2nd token in an expression, it can either be a 
		// 1. close bracket, ")" IF the expression has an open bracket as in "(a)", or else it MUST be a
		// 2. mathematic operator (+, -, *)
		if ( isCloseBracket(currentToken) ) {
			// 1. close bracket
			//cout << "Ran into a \")\" at currentPosition = " << *currentPosition - 1 << "\n";
			//cout << "numOfOpenBrackets = " << *numOfOpenBrackets << "\n";
			if ( *numOfOpenBrackets > 0 ) {
				// there was an open bracket to be closed, so this is valid.
				(*numOfOpenBrackets)--;
				return leftExpr; 
			} else {
				// there was no open bracket, so this is invalid!
				return NULL;
			}
		} else if (isMathOperator(currentToken)) {
			// 2. math operator
			TreeNodeType mathOperatorTNodeType = getMathOperatorTNodeType(currentToken);
			exprRoot = new TreeNode(mathOperatorTNodeType);
			exprRoot->addChild(leftExpr); // the left expr is always a child to this.
		} else {
			// anything else over here is invalid!
			return NULL;
		}

		// Done with the second token!
		// Now on to the 3rd token.
		// There MUST be a 3rd token, and the 3rd token MUST be the start of a valid expression!
		if ( *currentPosition > endPosition ) {
			return NULL;
		}
		if ( (*numOfOpenBrackets > 0) && (*currentPosition == endPosition) ) {
			// there was a bracket to be closed, but there is nothing left in the expression tokens!
			return NULL;
		}

		if (*currentPosition < endPosition) {
			std::string currentToken = exprTokens.at(*currentPosition);
			if ( isOpenBracket(currentToken) ) {
				isRightBracketed = true; // for use later
			}
		}
		// Get the right expression!
		rightExpr = convertExpressionToTreeRecursively(exprTokens, numOfOpenBrackets, currentPosition, endPosition);
		if (rightExpr == NULL) {
			//cout << "rightExpr is NULL for currentPosition = " << *currentPosition << "\n";
			// invalid expression on the right
			return NULL;
		}
		//cout << "rightExpr is not null for currentPosition = " << *currentPosition << "\n";
		
		// Reached the end but numOfOpenBrackets != 0
		if ( (*currentPosition > endPosition) && (*numOfOpenBrackets != 0) ) {
			// If (numOfOpenBrackets != numOfCloseBrackets), invalid expression!
			return NULL;
		} else {
			// Here, we have leftExpr as the child of exprRoot, and rightExpr not yet part of the tree.
			// Need to decide whether the current exprRoot will stay as the exprRoot,
			// or there is a need to set the exprRoot as the leftChild of the rightExpr to have the rightExpr be the new
			// exprRoot.
			// Such a situation arises when the precedence of the rightExpr math operator is lower than that of the current exprRoot.
			std::string exprRootOperator = translateTreeNodeTypeToMathOperator(exprRoot->getNodeType());
			std::string rightExprOperator = translateTreeNodeTypeToMathOperator(rightExpr->getNodeType());
			int precedence = compareMathOperators(exprRootOperator, rightExprOperator);
			// "x+y+z", "x+y*x*y+z", "y = y * (x - x) + y;"
			if ( rightExpr->getNumberOfChildren() == 0 || precedence < 0 || isRightBracketed ) {
				// precedence of the current exprRoot is lower than right,
				// so just add the rightExpr as the child of the current exprRoot
				exprRoot->addChild(rightExpr);
				return exprRoot;
			} else {
				// precedence of the rightExpr is lower than the current exprRoot,
				// so we have to do a few tree operations in order to correctly set
				// the exprRoot as the left child of the rightExpr.
				// 1. Traverse the rightExpr leftwards to the 2nd-bottom-left-most child node,
				// 2. Get the left child of the node found in (1) and
				// 3. Set the node gotten in (2) as the right child of the exprRoot and 
				// 4. Overwrite the left child of the node found in (1) to be the exprRoot and finally,
				// 5. Return the rightExpr.
				
				// 1. Traverse the rightExpr leftwards to the 2nd-bottom-left-most child node
				TreeNode *parent = rightExpr;
				TreeNode *child = rightExpr->getChild().at(0);
				std::string childOperator = translateTreeNodeTypeToMathOperator(child->getNodeType());
				while ( child->getNumberOfChildren() != 0 ) {
					if (precedence == 0) {
						// special case like for "x+y*z*y+x"
						if (compareMathOperators(exprRootOperator, childOperator) < 0) {
							break;
						}
					}
					// keep traversing!
					parent = child;
					child = child->getChild().at(0);
				}
				// Here, parent is the pointer to the 2nd-bottom-left-most child node!
				// 2. Get the left child of the node found in (1)
				// This node is just the child
				// 3. Set the node gotten in (2) as the right child of the exprRoot
				exprRoot->addChild(child);
				// 4. Overwrite the left child of the node found in (1) to be the exprRoot
				parent->addChildFront(exprRoot);
				parent->removeChildAtIndex(1);
				// 5. Return the rightExpr.
				return rightExpr;
			}
		}
}

std::string QueryExpressionParser::addSpacesToExpressionBeforeAndAfterMathSymbols(std::string expr) {
	std::string resultString = "";
	for (unsigned int i = 0; i < expr.length(); i++) {
		char c = expr.at(i);
		std::string s(1, c);
		if (isMathSymbol(c)) {
			// add a space before and after
			resultString.append(" ");
			resultString.append(s);
			resultString.append(" ");
		} else {
			// add normally
			resultString.append(s);
		}
	}
	return resultString;
}

std::vector<std::string> QueryExpressionParser::tokenizeByWhitespace(std::string expr) {
	std::vector<std::string> resultStrings;
	std::string currentString = "";
	bool isNonEmptyString = false;
	for (unsigned int i = 0; i < expr.length(); i++) {
		char c = expr.at(i);
		std::string s(1, c);
		if (s == " ") {
			if (isNonEmptyString) {
				resultStrings.push_back(currentString);
				currentString = "";
				isNonEmptyString = false;
			}
			continue;
		} else {
			currentString.append(s);
			isNonEmptyString = true;
		}
	}
	if (isNonEmptyString) {
		resultStrings.push_back(currentString);
	}
	return resultStrings;
}

std::vector<std::string> QueryExpressionParser::addBracketsAccordingToPrecedence(std::vector<std::string> exprTokens) {
	if ( exprTokens.size() == 0 ) {
		return std::vector<std::string>();
	}
	std::string firstToken = exprTokens.at(0);
	std::string lastToken = exprTokens.at(exprTokens.size()-1);
	if ( !isOpenBracket(firstToken) || !isCloseBracket(lastToken) ) {
		// add the bracket to the start and end
		exprTokens.insert(exprTokens.begin(), "(");
		exprTokens.push_back(")");
	}
	
	std::vector<std::string> prevExprTokens;
	int successSignal = 1;
	do {
		prevExprTokens = exprTokens;
		successSignal = addBracketsAccordingToPrecedenceRecursiveHelper(&exprTokens, 1, 1); // start immediately after the bracket
	} while ( (successSignal >= 0) && convertStringVectorToString(prevExprTokens) != convertStringVectorToString(exprTokens) );
	
	return exprTokens;
}

// Recursive helper function for the addImportantBracketsAccordingToPrecedence function.
// Returns an int denoting the position where it stopped checking.
int QueryExpressionParser::addBracketsAccordingToPrecedenceRecursiveHelper(std::vector<std::string> *exprTokens, unsigned int startPos, unsigned int addOpenBracketPosition) {
	//unsigned int addOpenBracketPosition = startPos;
	//unsigned int addOpenBracketPosition = addOpenBracketPos;
	unsigned int addCloseBracketPosition = startPos;
	unsigned int currentCheckPosition = startPos;
	unsigned int prevCheckPosition = startPos;
	unsigned int numOfMathOperatorsFound = 0; // everytime 2 operators are found without brackets being opened, there may be a need for brackets to be inserted
	std::string currentToken;
	std::string firstMathOperator;
	std::string secondMathOperator;
	bool addedBrackets = false;
	bool justRecursed = false;

	// This while loop ends upon one of the following conditions being met
	// 1. currentCheckPosition exceeds exprTokens size, returning -1 to signal an error with the expression
	// 2. a close bracket is met, returning the position of that close bracket
	// 3. brackets have been added once, at which it recursively adds brackets to the next section of tokens
	while ( currentCheckPosition < exprTokens->size() ) {
		if ( addedBrackets ) {
			// added brackets already
			firstMathOperator = secondMathOperator;
			if ( (currentCheckPosition + 1) < exprTokens->size() ) {
				secondMathOperator = exprTokens->at(currentCheckPosition + 1);
				if ( compareMathOperators(secondMathOperator, firstMathOperator) > 0 ) {
					addOpenBracketPosition = currentCheckPosition;
				}
			}
			return addBracketsAccordingToPrecedenceRecursiveHelper(exprTokens, currentCheckPosition, addOpenBracketPosition);
		}

		currentToken = exprTokens->at(currentCheckPosition);

		if ( isOpenBracket(currentToken) ) {
			// recurse
			prevCheckPosition = currentCheckPosition;
			currentCheckPosition = addBracketsAccordingToPrecedenceRecursiveHelper(exprTokens, (currentCheckPosition + 1), (currentCheckPosition + 1));
			justRecursed = true;
		} else if ( isCloseBracket(currentToken) ) {
			// since this recursive helper is called for each open bracket, it ends at each close bracket
			// return the next position to be checked
			return currentCheckPosition;
		} else if ( isMathOperator(currentToken) ) {
			numOfMathOperatorsFound++;

			if ( numOfMathOperatorsFound == 1 ) {
				firstMathOperator = currentToken;
			} else if ( numOfMathOperatorsFound == 2 ) {
				secondMathOperator = currentToken;
				// 1 + 2 * (3+4)
				// choose where to place the brackets, depending on precedence
				 if ( compareMathOperators(firstMathOperator, secondMathOperator) >= 0 ) {
					 // if the first math operator has higher or equal precedence, 
					 // the brackets are placed around to encapsulate the first math operator
					 // and the left and right arguments
					 addCloseBracketPosition = currentCheckPosition;
					 exprTokens->insert( (exprTokens->begin() + addCloseBracketPosition), ")");
					 exprTokens->insert( (exprTokens->begin() + addOpenBracketPosition), "(");
					 
					 // 2 elements have been added, so increase the currentCheckPostion
					 currentCheckPosition += 2;

					 addedBrackets = true;
				 } else {
					 // if the second math operator has higher precedence,
					 // then just reset everything in preparation for the next iteration
					 addOpenBracketPosition = prevCheckPosition;
					 addCloseBracketPosition = prevCheckPosition;
					 firstMathOperator = secondMathOperator;
					 numOfMathOperatorsFound = 1;
				 }
			}
		} 

		if ( !justRecursed ) {
			prevCheckPosition = currentCheckPosition;
		} else {
			// just recursed, the prevCheckPosition does not change
			justRecursed = false;
		}
		currentCheckPosition++;
	}

	// If we are out of the loop, the math expression must have been invalid (lack of close brackets)
	return -1;
}

int QueryExpressionParser::compareMathOperators(std::string operator1, std::string operator2) {
	if ( !isMathSymbol(operator1) || !isMathSymbol(operator2) ){
		return 0;
	} else {
		int op1Precedence = mMapOfMathSymbols.at(operator1);	
		int op2Precedence = mMapOfMathSymbols.at(operator2);
		return (op1Precedence - op2Precedence);
	}
}

// Returns the math operator tree node type (e.g. AST_MINUS) based on the math operator that is
// represented by token.
// Returns AST_INVALID_TYPE if token is not a representation of a math operator as defined in the mMapOfMathOperators.
TreeNodeType QueryExpressionParser::getMathOperatorTNodeType(std::string token) {
	if ( mMapOfMathOperators.find(token) == mMapOfMathOperators.end() ) {
		return AST_INVALID_TYPE;
	} else {
		return mMapOfMathOperators.at(token);
	}
	return AST_INVALID_TYPE;
}

bool QueryExpressionParser::isMathSymbol(std::string s) {
	if (mMapOfMathSymbols.find(s) == mMapOfMathSymbols.end()) {
		return false;
	} else {
		return true;
	}
}

bool QueryExpressionParser::isMathSymbol(char c) {
	std::string s(1, c);
	return isMathSymbol(s);
}

bool QueryExpressionParser::isMathOperator(std::string s) {
	if (mMapOfMathOperators.find(s) == mMapOfMathOperators.end()) {
		return false;
	} else {
		return true;
	}
}

bool QueryExpressionParser::isMathOperator(char c) {
	std::string s(1, c);
	return isMathOperator(s);
}

// Returns true if the startingToken is valid for a mathematical expression in SPA.
// e.g. "a" or "myVariable" or "1" or "(" are valid as long as "a" and "myVariable" exist in the PKB as variables.
bool QueryExpressionParser::isValidStartingToken(std::string startingToken) {
	if ( isOpenBracket(startingToken) || isConstantInteger(startingToken) ||
			isValidVariableName(startingToken) ) {
				
				//cout << "startingToken \"" << startingToken << "\" is valid!\n";
				return true;
	} else {
		//cout << "startingToken \"" << startingToken << "\" is invalid!\n";
		return false;
	}
}

// Returns true if the token is "(", false otherwise.
bool QueryExpressionParser::isOpenBracket(std::string token) {
	if (token == "(") {
		return true;
	} else {
		return false;
	}
}

// Returns true if the token is ")", false otherwise.
bool QueryExpressionParser::isCloseBracket(std::string token) {
	if (token == ")") {
		return true;
	} else {
		return false;
	}
}

// Returns true if the token is integer-parseable, false otherwise.
bool QueryExpressionParser::isConstantInteger(std::string token) {
	if (token.length() == 0) {
		return false;
	}
	for (unsigned int i = 0; i < token.length(); i++) {
		char c = token.at(i);
		if (!isDigit(c)) {
			return false;
		}
	}
	return true;
}

// Returns true if the token is a valid variable name, false otherwise.
// A valid variable name starts with an alphabet from a-z or A-Z,
// and can be followed by more alphabets or digits (0-9)
bool QueryExpressionParser::isValidVariableName(std::string token) {
	if (token.length() == 0) {
		return false;
	}
	// Here, the token has at least one character :)
	char firstChar = token.at(0);
	if ( !isAlphabet(firstChar) ) {
		return false;
	}
	// Here, the token has the first character as an alphabet :)
	for (unsigned int i = 1; i < token.length(); i++) {
		char c = token.at(i);
		if ( !isAlphabet(c) && !isDigit(c) ) {
			// the following characters in a valid variable name MUST be either an alphabet or a digit!
			return false;
		}
	}
	return true;
}

// Returns true if c is an alphabet a-z or A-Z, false otherwise.
bool QueryExpressionParser::isAlphabet(char c) {
	if ( (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ) {
		return true;
	} else {
		return false;
	}
}

// Returns true if c is a digit from 0-9, false otherwise.
bool QueryExpressionParser::isDigit(char c) {
	if ( c >= '0' && c <= '9' ) {
		return true;
	} else {
		return false;
	}
}

// Gets the variable index of the token from the mPKB.
// Note: -1 is returned if the token does not exist in the mPKB's varTable.
int QueryExpressionParser::getVariableIndexFromPKB(std::string token) {
	return mPkb->getVarIndex(token);
}

// Returns a string representing the math operator of the given nodeType.
// Returns an empty "" string if nodeType does not represent any math operator.
// e.g. nodeType AST_MINUS returns "-" as defined in the mMapOfMathOperators.
std::string QueryExpressionParser::translateTreeNodeTypeToMathOperator(TreeNodeType nodeType) {
	for (std::map<std::string, TreeNodeType>::iterator it = mMapOfMathOperators.begin(); it != mMapOfMathOperators.end(); it++) {
		if (it->second == nodeType) {
			return it->first;
		}
	}
	return "";
}

std::string QueryExpressionParser::convertStringVectorToString(std::vector<std::string> stringVector) {
	std::string str;
	for (unsigned int i = 0; i < stringVector.size(); i++) {
		str.append(stringVector.at(i));
	}
	return str;
}